
#include<iostream>
#include<windows.h>
using namespace std;

typedef int elem;
class Dlist{
    private:
        elem data; //存储数据
        Dlist* next; //指向后一个元素
        Dlist* front;//指向前一个元素
    public:
        Dlist(elem _data):data(_data),next(NULL),front(NULL){}
        Dlist():data(0),next(NULL),front(NULL){}

        Dlist* insert(elem msg,Dlist *head);//插入一条数据到链表,尾插法
        Dlist* insertback(elem msg, Dlist* tail);//头插法

        Dlist* CreateList(); //创建一个链表

        void dele(elem msg,Dlist *head);//根据头指针删除某个数据
        void dele2(elem msg,Dlist *tail);//根据尾指针删除某个数据

        void Search(elem msg,Dlist *head); 
        void show(Dlist *head); //输出链表数据
};


//采用尾插法
 Dlist* Dlist::insert(elem msg,Dlist *phead){
    Dlist *q=new Dlist(msg);
     if(phead->next==NULL){
        phead->next=q;
        q->front=phead;
        return phead;
     }
     else{
        Dlist *tail=phead;
        while(tail->next!=NULL){
            tail=tail->next;
        }
        tail->next=q;
        q->front=tail;
        return phead;
     }
}

//采用头插法
Dlist* Dlist::insertback(elem msg,Dlist* tail){
    Dlist *q=new Dlist(msg);
    q->front=tail->front;
    q->next=tail;
    tail->front=q;
    return tail;
}

Dlist* Dlist::CreateList(){
    int data;
    int num=0;
    cout<<"请输入要创建的链表元素个数"<<endl;
    cin>>num;
    cout<<"请输入对应的元素："<<endl;
    Dlist node=Dlist(0);
    Dlist *head=new Dlist(0);
    for(int i=0;i<num;i++){
        cin>>data;
        head=node.insert(data,head);
    }
    return head;

}

//根据头指针删除某个结点
void  Dlist::dele(elem msg,Dlist *phead){
    if(phead==NULL){
        cout<<"链表为空"<<endl;
    }
    else{
        Dlist* tail=phead;
        tail=tail->next;
        while(tail!=NULL){
            if(tail->data==msg){
                if(tail->next!=NULL){
                    Dlist* node=tail->next;
                    node->front=tail->front;
                    tail->front->next=node;
                    delete(tail);
                    break;
                }
                else{
                    tail->front->next=NULL;
                    delete(tail);
                    break;
                }
            }
            tail=tail->next;
        }
    }
}

//根据尾指针删除某个元素
void Dlist::dele2(elem msg,Dlist* tail){
    if(tail->front==NULL){
        cout<<"链表为空"<<endl;
    }
    else{
        Dlist *node=tail->front;
        while(node!=NULL){
            if(node->data==msg){
                if(node->front!=NULL){
                    Dlist* a=node->front;
                    a->next=node->next;
                    node->next->front=a;
                    delete(node);
                    cout<<"删除成功"<<endl;
                    break;   }
                else{
                    Dlist* a=node->next;
                    delete(node);
                    cout<<"删除成功"<<endl;
                    break;
                    }
            }
            node=node->front;
        }
    }
}

void Dlist::Search(elem msg,Dlist *phead){
        while(phead!=NULL){
        if(phead->data==msg){
            cout<<"查找成功"<<endl;
        }
        phead=phead->next;
        }
        cout<<"不存在该元素"<<endl;    
}

void Dlist::show(Dlist *head){
    head=head->next;
    while (head!=NULL)
    {
        cout<<head->data<<"->";
        head=head->next;
    }
    cout<<"NULL"<<endl;
}

int main(){
    SetConsoleOutputCP(CP_UTF8);

    Dlist node=Dlist(0);
    Dlist *head=node.CreateList();
    node.show(head);
    cout<<"输入要删除的数据"<<endl;
    elem s;
    cin>>s;
    node.dele(s,head);
    node.show(head);
/*
    Dlist node2=Dlist();
    Dlist *tail=new Dlist();
    tail=node2.insertback(10,tail);
    tail=node2.insertback(20,tail);
    tail=node2.insertback(30,tail);
    node2.dele2(20,tail);  */

}